package com.ming.learn.from.carl.binary.tree;

import com.ming.commons.utils.Node;
import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
559.N叉树的最大深度
 */
public class Of20210307LeetCode559 {
    /*
    给定一个 N 叉树，找到其最大深度。
    最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
     */
    public static void main(String[] args) {
        Node node = new Node(1, Arrays.asList(new Node(2, Arrays.asList(new Node(5)
                , new Node(6))), new Node(3, Arrays.asList(new Node(7,Arrays.asList(new Node(9))))), new Node(4, Arrays.asList(new Node(8)))));
        System.out.println(maxDepth2(node));
    }

    /*
    递归法
     */
    private static int maxDepth(Node root) {
        if (root == null) return 0;

        int depth = 0;
        for (int i = 0; i < root.children.size(); i++) {
            depth = Math.max(depth, maxDepth(root.children.get(i)));
        }
        return depth + 1;
    }

    /*
    迭代法
     */
    private static int maxDepth2(Node root) {
        ArrayQueue<Node> queue = new ArrayQueue<>(10);
        if (root != null) queue.add(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node node = queue.remove(0);
                for (int j = 0; j < node.children.size(); j++) {
                    if (node.children.get(j) != null) queue.add(node.children.get(j));
                }
            }
        }
        return depth;
    }
}
